package lianxi;

import java.util.*;

public class demo10 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode deleteNode(ListNode head, int val) {
            if (head.val==val){
                return head.next;
            }
            ListNode curnode=head.next;
            ListNode pre=head;
            while (curnode!=null&&curnode.val!=val){
                pre=curnode;
                curnode=curnode.next;
            }

    pre.next = curnode.next;

            return head;
        }



        public int[] reversePrint(ListNode head) {
            Stack<ListNode> stack=new Stack<>();
            ListNode curnode=head;
            while (curnode!=null){
                stack.push(curnode);
                curnode=curnode.next;
            }
            int a[]=new int[stack.size()];
            for (int i = 0; i < stack.size(); i++) {
                a[i]=stack.pop().val;
            }
            return a;
        }



        public boolean hasCycle(ListNode head) {
            Set<ListNode> set=new HashSet<>();
            while (head!=null){
                if(!set.add(head)){
                    return true;
                }
                head=head.next;
            }
            return false;
        }



        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set=new HashSet<>();
        while (headA!=null){
            set.add(headA);
            headA=headA.next;
        }
        while (headB!=null){
            if (set.contains(headB)){
                return headB;
            }
            headB=headB.next;
        }
        return null;
        }


        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
               ListNode dum=new ListNode();
               ListNode cur=dum;
               while (l1!=null&&l2!=null){
                   if(l1.val<=l2.val){
                       cur.next=l1;
                       l1=l1.next;
                   }
                   else{
                       cur.next=l2;
                       l2=l2.next;
                   }
                   cur=cur.next;
               }
               cur.next=l1!=null?l1:l2;
              return dum.next;
        }


        public ListNode reverseList(ListNode head) {
          if(head==null){
              return head;
          }
          ListNode reverse=null;
          ListNode cur=head;
          while (cur!=null){
              ListNode temp=cur.next;
              cur.next=reverse;
              reverse=cur;
              cur=temp;
          }
        return reverse;

        }


        public boolean isPalindrome(ListNode head) {


        List<Integer> list=new ArrayList<>();
            ListNode cur=head;
         while (cur!=null){
             list.add(cur.val);
             cur=cur.next;
         }
         int start=0;
         int end=list.size()-1;
         while (start<end){
             if(!list.get(start).equals(list.get(end))){
                 return false;
             }
             start++;
             end--;
         }
         return true;
        }
}
}
